package util.math;

public class LevenshteinDistance {
	private static int minimum(int a, int b, int c) {
		if (a <= b && a <= c)
			return a;
		if (b <= a && b <= c)
			return b;
		return c;
	}
	
	public static float getSimilarity(String str1, String str2){
		int d = LevenshteinDistance.computeLevenshteinDistance(str1, str2);
		return 100-(((float)d/((float)(str1.length()+str2.length())/2))*100);
	}
	
	public static int computeLevenshteinDistance(String str1, String str2) {
		return computeLevenshteinDistance(str1.toCharArray(), str2
				.toCharArray());
	}

	private static int computeLevenshteinDistance(char[] str1, char[] str2) {
		int[][] distance = new int[str1.length + 1][str2.length + 1];

		for (int i = 0; i <= str1.length; i++)
			distance[i][0] = i;

		for (int j = 0; j <= str2.length; j++)
			distance[0][j] = j;

		for (int i = 1; i <= str1.length; i++)
			for (int j = 1; j <= str2.length; j++)
				distance[i][j] = minimum(distance[i - 1][j] + 1,
						distance[i][j - 1] + 1, distance[i - 1][j - 1]
								+ ((str1[i - 1] == str2[j - 1]) ? 0 : 1));

		return distance[str1.length][str2.length];
	}
	
	public static void main(String[]args){
		String[][] word={
				{"Paralelepipedo","Paralelepupodo"},
				{"a","b"},
				{"hola","ola"},
				{"balbabla","blablablabla"},
				{"cólera","colera"},
				{"PROG. ORIENTADA A OBJ.","PROGRAMACION ORIENTADA A OBJETOS"},
				{"TEORIA DE SIST.","TEORIA DE SISTEMAS"},
				{"PREBENCION DE RIESGOS","PREB. DE RIESGOS"},
				{"ALG. LINEAL","ALGEBRA LINEAL"},
				{"CALC. EN VARIAS VARIABLES","CALCULO EN VARIAS VARIABLES"},
				{"CALC. EN VARIAS VARIABLES","CALCULO EN UNA VARIABLE"},
				{"CALC. EN UNA VARIABLE","CALCULO EN VARIAS VARIABLES"},
				{"CALC. EN UNA VARIABLE","CALC. EN UNA VARIABLE"},
				{"CALC. EN UNA VARIABLE","CALCULO EN UNA VARIABLE"},
				{"Canción","Maleta"},
				{"arbusto","comida"},
				};
		
		for (int i = 0; i < word.length; i++) {
			int d = LevenshteinDistance.computeLevenshteinDistance(word[i][0], word[i][1]);
			float dissimilarity = ((float)d/((float)(word[i][0].length()+word[i][1].length())/2))*100,similarity=100-dissimilarity;
			System.out.println("---------------------------------------------------------------------");
			System.out.println("For \""+word[i][0]+"\" and \""+word[i][1]+"\" the distance is "+d+".");
			System.out.println("\t Dissimilarity = "+dissimilarity+".");
			System.out.println("\t Similarity = "+similarity+".");
		}
	}
}

